/*
 * MatrixColumnCoverILP
 *
 * Version: 0.1
 *
 * 2011-08-23
 */

package gss.ilp;

import ilog.cplex.IloCplex;
import ilog.concert.IloIntExpr;
import ilog.concert.IloIntVar;
import ilog.concert.IloException;

import java.util.List;
import java.util.ArrayList;

import java.util.regex.Pattern;
import java.util.Scanner;

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

/**
 * MatrixColumnCoverILP reads a 0-1 matrix from standard input and finds the
 * minimum number of rows necessary to cover all columns with 1's, printing the
 * solution to standard output.  Errors are reported as non-positive output
 * value along with a non-zero exit status.  If the <code>-v</code> flag is
 * given then a line is printed for every row in the input consisting of a 1 if
 * the corresponding row was used in the optimal cover and 0 otherwise.  At the
 * moment the covering is done with IBM ILOG CPLEX's mixed integer linear
 * programming (MILP) faciilities.  The matrix is assumed to be rectangular and
 * non-sparse, and out-of-bounds exceptions may occur if this assumption is
 * violated.
 */
public class MatrixColumnCoverILP { 

    private IloCplex cplex;
    private ArrayList<IloIntExpr> exprs;
    private ArrayList<IloIntVar> vars;

    private static enum OutputType {
        NUMERIC,            // number of rows in the optimal cover
        BINARY_ROWS;        // one line per row, 1 if it was in the cover, 0
                            // otherwise
    }

    public MatrixColumnCoverILP() throws IloException {
        cplex = new IloCplex();
        exprs = new ArrayList<IloIntExpr>();
        vars = new ArrayList<IloIntVar>();

        // redirect the CPLEX output to stderr to avoid polluting stdout
        cplex.setOut(System.err);
    }

    public static void main(String[] args) throws IloException, IOException {
        OutputType output_type = OutputType.NUMERIC;

        // test presence of -v flag and set output_type accordingly
        if (args.length > 0 && args[0].equals("-v")) {
            output_type = OutputType.BINARY_ROWS;
        }

        BufferedReader reader
            = new BufferedReader(new InputStreamReader(System.in));

        MatrixColumnCoverILP ilp = new MatrixColumnCoverILP();
        ilp.buildColumnCoverModel(reader);

        if (ilp.cplex.solve()) {
            if (!ilp.cplex.getStatus().equals(IloCplex.Status.Optimal)) {
                System.out.println("-1");
                return;
            }

            // else we have a good solution
            switch (output_type) {
                case NUMERIC:
                    System.out.println((int) ilp.cplex.getObjValue());
                    break;
                case BINARY_ROWS:
                    for (IloIntVar x: ilp.vars) {
                        System.out.println((int) ilp.cplex.getValue(x));
                    }
                    break;
                default:
                    System.err.println("Invalid output type");
                    break;
            }

            System.err.println("Objective: " + ilp.cplex.getObjective().getExpr());
        } else {
            System.out.println("-1");
            return;
        }
    }

    /**
     * @param reader    source of matrix input
     * @return IloCplex representing the column cover problem in the input matrix
     */
    private IloCplex buildColumnCoverModel(BufferedReader reader)
            throws IloException, IOException {
        Pattern p = Pattern.compile("[01]");
        Scanner s;
        String line;
        int i;

        /* use the first line to find the number of columns, then process the
         * rest of the input in a do-while loop */
        if ((line = reader.readLine()) != null) {
            // compute number of columns, 'i', from first line
            s = new Scanner(line);
            i = 0;
            while (s.hasNext(p)) {
                i++;
                s.next(p);
            }

            // initialize expr array to empty int expr
            for (; i>0; --i) {
                exprs.add(cplex.intExpr());
            }

            // process the rest of the input
            do {
                s = new Scanner(line);
                IloIntVar x = cplex.boolVar();
                vars.add(x);
                i = 0;
                while (s.hasNext(p)) {
                    String c = s.next(p);       // c = "0" or "1"
                    if (c.equals("1")) {        // exprs[i] += x
                        exprs.set(i, cplex.sum(exprs.get(i), x));
                    }
                    ++i;
                }
            } while ((line = reader.readLine()) != null);

            // add the minimize objective
            cplex.addMinimize(cplex.sum(vars.toArray(new IloIntExpr[0])));

            // add all (exprs >= 1) constraints to model, meaning every column
            // must be covered at least once
            for (IloIntExpr expr : exprs) {
                cplex.addGe(expr, 1.0);
            }

            System.err.println("Total: " + vars.size() + " variables");
            System.err.println("Total: " + exprs.size() + " constraints");
        }

        return cplex;
    }

}

